package com.shujujiegou.无权无向图.搜索.简单实现;

import com.shujujiegou.无权无向图.搜索.实现广度优先搜索的队列.StackX;
import com.shujujiegou.无权无向图.搜索.实现深度优先搜索的栈.Queue;

public class Graph {
    private final int MAX_VERTS = 20; // 表示顶点的个数
    private Vertex vertexList[]; // 存储顶点的数组
    private int adjMat[][]; // 用邻接矩阵来存储边，0： 没边界， 1：有边界
    private int nVerts; // 顶点个数
    private StackX stackx; // 用栈实现深度搜索
    private Queue queue; // 用队列实现广度搜索

    /**
     * 顶点类
     */
    private class Vertex{
        public char label; // 用来表示顶点的字符
        public boolean wasVisited; // 表示顶点有没有被访问过

        public Vertex(char label) {
            this.label = label;
            this.wasVisited = false;
        }
    }

    public Graph() {
        vertexList = new Vertex[MAX_VERTS];
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0; // 初始化顶点个数
        // 初始化邻接矩阵所有元素都为0， 即都没有边
        for(int i = 0; i < MAX_VERTS; ++i) {
            for(int j = 0; j < MAX_VERTS; ++j) {
                this.adjMat[i][j] = 0;
            }
        }
        this.stackx = new StackX();
        this.queue = new Queue();
    }

    // 将顶点添加到数组中，是否访问标志置为未访问
    public void addVerts(char lable) {
        this.vertexList[this.nVerts++] = new Vertex(lable);
    }

    // 增加边，注意使用邻接矩阵的时候，是对称的，两边都要赋值
    public void addEdge(int start, int end) {
        this.adjMat[start][end] = 1;
        this.adjMat[end][start] = 1;
    }

    // 打印某个顶点表示的值
        public void display(int index) {
            if(index < this.nVerts) {
                System.out.print(this.vertexList[index].label);
            }
    }

    /**
     * 深度优先算法
     */
    public void deepFirstSearch() {
        if(this.nVerts <= 0) {
            return;
        }

        this.vertexList[0].wasVisited = true; // 从第一个顶点开始
        this.stackx.push(0); // 将第一个顶点放入栈中
        this.display(0);

        while(!this.stackx.isEmpty()) {
            // 找到当前顶点邻接且未被访问的顶点
            int v = getAdjUnionVertex(this.stackx.peek());
            if(v != -1) { // 如果存在未被访问的顶点与当前顶点连接，则放入栈中，并且设置未已被访问
                this.vertexList[v].wasVisited = true;
                this.stackx.push(v);
                this.display(v);
            } else {
                this.stackx.pop(); // 如果没有未被访问的顶点与当前顶点连接，则出栈当前顶点
            }
        }

        // 栈访问完毕，重置所有标记位
        for(int i = 0; i < this.nVerts; ++i) {
            this.vertexList[i].wasVisited = false;
        }
    }

    // 找到与某一顶点邻接且未被访问的顶点
    public int getAdjUnionVertex(int v) {
        for(int i = 0; i < this.nVerts; ++i) {
            // 如果 v 与 i 相邻， 且未被访问
            if(this.adjMat[v][i] == 1 && this.vertexList[i].wasVisited == false) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 广度优先搜索算法
     */
    public void breadthFirstSearch() {
        if(this.nVerts <= 0) {
            return;
        }

        this.vertexList[0].wasVisited = true;
        this.queue.insert(0);
        this.display(0);
        int v2;

        while(!this.queue.isEmpty()) {
            int v1 = this.queue.remove();
            while((v2 = getAdjUnionVertex(v1)) != -1) {
                this.vertexList[v2].wasVisited = true;
                this.queue.insert(v2);
                this.display(v2);
            }
        }

        // 栈访问完毕，重置所有标记位
        for(int i = 0; i < this.nVerts; ++i) {
            this.vertexList[i].wasVisited = false;
        }
    }

    /**
     * 对于图的操作，还有一个最常用的就是找到最小生成树，
     * 最小生成树就是用最少的边连接所有顶点。对于给定的一组顶点，
     * 可能有很多种最小生成树，但是最小生成树的边的数量 E 总是比顶点 V 的数量小1，即：
     *
     * 　　V = E + 1
     *
     * 　　这里不用关心边的长度，不是找最短的路径（会在带权图中讲解），
     *     而是找最少数量的边，可以基于深度优先搜索和广度优先搜索来实现。
     *
     * 　　比如基于深度优先搜索，我们记录走过的边，就可以创建一个最小生成树。因为DFS 访问所有顶点，
     *     但只访问一次，它绝对不会两次访问同一个顶点，但她看到某条边将到达一个已访问的顶点，
     *    它就不会走这条边，它从来不遍历那些不可能的边，因此，DFS 算法走过整个图的路径必定是最小生成树。
     */
    public void mst() { //基于深度优先搜索找到最小生成树
        if(this.nVerts <= 0) {
            return;
        }

        this.vertexList[0].wasVisited = true;
        this.stackx.push(0);

        while(!this.stackx.isEmpty()) {
            int currentVertex = this.stackx.peek();
            int v = this.getAdjUnionVertex(currentVertex);
            if(-1 != v) {
                this.stackx.push(v);
                this.vertexList[v].wasVisited = true;
                this.display(currentVertex);
                this.display(v);
                System.out.print(" ");
            } else {
                this.stackx.pop();
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVerts('A');
        graph.addVerts('B');
        graph.addVerts('C');
        graph.addVerts('D');
        graph.addVerts('E');

        graph.addEdge(0, 1);//AB
        graph.addEdge(1, 2);//BC
        graph.addEdge(0, 3);//AD
        graph.addEdge(3, 4);//DE

        System.out.println("深度优先搜索算法 :");
        graph.deepFirstSearch();//ABCDE

        System.out.println();
        System.out.println("----------------------");

        System.out.println("广度优先搜索算法 :");
        graph.breadthFirstSearch();//ABDCE

        System.out.println();
        System.out.println("----------------------");

        System.out.println("最小生成树 :");
        graph.mst();//AB BC AD DE
    }
}
